1. Field of the Invention
The present invention generally relates to access methods for wireless networks and, more particularly, to protocols used in accessing the shared wireless media.
2. Description of the Prior Art
A wireless network is a way of associating, or grouping, portable devices which communicate with each other via radio frequency (RF) signals or infrared (IR) light signals. Wireless networks are more flexible and cheaper to install than wired networks, and the emergence of portable terminals in work, living ant traveling environments is accelerating the embracing of wireless networks.
In general, a specific medium access control (MAC) protocol is implemented in order to access and share a medium in an organized and efficient fashion. In essence, the MAC protocol ensures that only one station at a time is permitted to access a certain channel on the medium. However, in wireless networks, each station has a unique view of the medium; i.e., the channel properties viewed from station A can not be expected to be identical to the channel properties as viewed from another station B. This is in stark contrast to wired networks, where all stations have about the same view of the channel conditions. The reason for the unique channel view in wireless networks is caused by the fact that the medium is not confined within any well defined physical boundaries. Thus, there is no control over signal levels, noise levels and interference levels. One of the side effects of this is a phenomenon known as the "hidden node" or "hidden terminal" problem.
FIG. 1 illustrates the problem. In order to explain FIG. 1, we need to introduce the term "communications range". Communications range is the maximum distance between two stations where the two stations can communicate without errors. This distance is dependent on a number of factors, such as the launched signal level at the transmitter station, the noise level at the receiver station, the strength of interfering signals at the receiver, and the physical orientation of the transmitter and receiver units, FIG. 1 further assumes that all six stations share the same channel. This means that only one station at a time is allowed to access the channel. The other stations become observers; i.e., they are in deferred mode.
FIG. 1 shows six stations A, B, C, D, E, and F. The solid lines show which station pairs are within communications range of each other. (In addition, the fat lines indicate which stations have set up logical connections with each other, which we shall use later on.) For example, stations C and D can communicate and stations D and E can communicate. But stations E and C can not communicate and stations E and B can not communicate.
Whether two stations can communicate or not depends on the particular value of the "communications range" which, in general, will be different for each station pair. In FIG. 1, stations A and E are said to be "hidden" from each other with respect to station D with which they can both communicate. Similarly, stations B and D are hidden from each other with respect to station C (as well as station A) with which they can both communicate.
Hidden nodes are common in IR Systems, especially if the IR system is a so called directed system where the transmitters launch power within certain angles and where there has to be line-of-sight between two communicating stations.
It has been found, both experimentally and theoretically, that if stations A and B are communicating with each other, and stations C and D are communicating with each other, and stations E and F are communicating with each other, then the middle station pair (C,D) has zero throughput when all stations constantly has data queued up for transmission. The reason for this is the unbalanaced view of the channel as seen from each station. The (C,D) station pair observes traffic from both station pair (A,B) and from station pair (E,F), but station pair (A,B) only sees traffic from station pair (C,D) and so does station pair (E,F). Due to the dynamics of the system, only station pairs (A,B) and (E,F) will he able to access the channel because station pair (C,D) end up being observers most of the time. This problem is classified as a "fairness" problem, and hidden nodes is the main cause for this fairness problem.
The six station example presented here is a very serious fairness problem as literally the middle station pair may never access the medium; i.e., they will have zero throughput. Solutions for this kind of fairness problem has not yet been addressed in the prior art. A fairness problem of a much less serious nature has been addressed by Vaduvur Bharghavan, Alan Demers, Scott Shenker and Lixia Zhang in "MACAW: A Media Access Protocol for Wireless LANs", ACM-SIGCOMM '94, pp. 212-224, from the perspective of obtaining per-stream fairness in a client-server configuration, in which separate queues for each logical connection are implemented and each queue has its own back-off algorithm. Bharghavan et al. also proposed a back off window size exchange method which attempted to synchronize all stations to use the same window size for the calculation of their back off values. In general, Bharghavan et al. focused on improving the channel throughput; i.e., the sum of all stations' throughput. Bharghavan et al. did not address the issue of preventing zero access to the network at any station and for any topology.